Chris Pollett > Old Classses >
CS156
( Print View )

Student Corner:
  [Grades Sec1]

  [Submit Sec1]

  [Lecture Notes]

  [Discussion Board]

Course Info:
  [Texts & Links]
  [Topics/Outcomes]
  [Outcomes Matrix]
  [Grading]
  [HW/Quiz Info]
  [Exam Info]
  [Regrades]
  [Honesty]
  [Additional Policies]
  [Announcements]

HWs and Quizzes:
  [Hw1]  [Hw2]  [Hw3]
  [Hw4]  [Hw5]  [Quizzes]

Practice Exams:
  [Mid]  [Final] 

                           












HW#5 --- last modified February 07 2019 04:21:11..

Solution set.

Due date: Dec 10

Files to be submitted:
  Project.zip

Purpose: To get more familiar with probabilistic inference and learning algorithms.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO12 -- Students should be able to describe or implement at least one learning algorithm

Specification:

This homework will consist of both a written and coding part. Submit the written part in a file Hw1.pdf as part of your zip. It should consist of answers to the following questions:

  1. Consider the following partially explored Wumpus World (ignore how we ended up with a world explored in this fashion):
         
    B   
    XB  
    XXS 
    Here `X` indicates explored but nothing detected; `B` indicates a breeze was felt on that square; `S` indicates a stench was smelt. For each square on the frontier use the method from the Nov 19 Lecture to get a probability that the given square is safe. Which square should a rational agent who must find the gold search next?
  2. Consider the following table of data concerning whether or not a person was a movie star:
    Plastic SurgeryTeeth ColorManicurePedicureIs Movie Star
    FaceLiftYellowNoNoNo
    NoneWhiteYesYesYes
    NoseJobWhiteNoYesYes
    Work out by hand (show work) the decision tree that our decision tree learning algorithm would compute for the above training set.

For the coding part of the assignment I would like you to code the perceptron learning algorithm discussed in class and use it to learn the concept of connected versus unconnected grid. Your program will be run from the command line with a line like:

python connect_learner.py training_file_name.txt test_file_name.txt

training_file_name.txt is the name of a file containing the training set for the algorithm, test_file_name.txt is the name of a file containing a grid which we want to classify as connected or not. Your program on such an input can output whatever diagnostic messages you deem useful, however, the last line it outputs should be either the single word CONNECTED (if its connected) or DISCONNECTED (if its not connected). The file format for the training set is as follows:

[EXAMPLE]
newline character
[EXAMPLE]
...
newline character
[EXAMPLE]
Things on seperate lines above have newlines after them. So after the last character of an [EXAMPLE] there two newline characters before the next example. Here [EXAMPLE] has the format: 
[GRID]
[CLASSIFICATION]
[CLASSIFICATION] is either the word CONNECTED or the word DISCONNECTED. [GRID] has the format: 
[GRID_LINE]
[GRID_LINE]
[GRID_LINE]
[GRID_LINE]
[GRID_LINE]
where [GRID_LINE] has the format: 
[GRID_VALUE][SPACE][GRID_VALUE][SPACE][GRID_VALUE][SPACE][GRID_VALUE][SPACE][GRID_VALUE]
[SPACE] is a single space character, [GRID_VALUE] is either O for occupied or X for unoccupied. So a [GRID] is a 5x5 matrix of space separated entries which are either O or X. We say such a grid is connected if whenever there are two distinct O's in the grid they are connected by a path of adjacent squares (no diagonal moves) which are all labeled O. Below is a concrete file that serves as an example training set: 
X X X X X
O X X X X
X X X X X
X X X X X
X X X X X
CONNECTED

X X X X X
O X X X X
X X X X X
X X X X O
X X X X X
DISCONNECTED

X X O X X
O X O X X
O O O O X
X X O O O
X X O X X
CONNECTED
The file test_file_name.txt consists of just a [GRID]. As part of your project you should conduct some experiments by randomly generating training sets of different sizes and experimentally determining successful classification percentages for each of these sizes. Write up these experiments in the file Experiments.pdf which you also include with your project.

Point Breakdown

Written problems (2pts each - each documented flaw 1/2pt off) 4pts
connect_learner.py reads in files corrected and outputs CONNECTED or DISCONNECTED 1pt
connect_learner.py implements the perceptron algorithm described in class. 3pts
Random grid code to test connect_learner.py as well as documentation explaining how it works/was used. 1pt
Experiments.pdf contains a reasonable write-up of experiments conducted. 1pt
Total10pts